#include <stdlib.h>
#include <stdio.h>


#include "tree.h"
struct node {
	ElementType ele;
	Tree left;
	Tree right;
};

PtrToNode newNode(ElementType x) {
	PtrToNode aNode = (PtrToNode) malloc(sizeof(Node));
	aNode->ele = x;
	aNode->left = NULL;
	aNode->right = NULL;
	// printf("create node %.2f\n", x);
	return aNode;
}

PtrToNode freeNode(PtrToNode aNode) {
	if (aNode == NULL)return;
	aNode->left = NULL;
	aNode->right = NULL;
	free(aNode);
}

// Tree Delete(Tree t, ElementType x);
ElementType retrieve(PtrToNode node) {
	return node->ele;
}

// if 1:x>y, 0 x=y, -1 x<y
int compare(ElementType x, ElementType y) {
	if (x > y) return 1;
	return x < y ? -1 : 0;
}

void printNode(PtrToNode aNode) {
	if (aNode == NULL) {
		printf("error:NULL node\n");
		return;
	}

	ElementType ele = retrieve(aNode);
	printf("%.1f\n", ele);
}

Tree insert(Tree t, ElementType x) {
	if (t == NULL) return newNode(x);
	int cmp = compare(x, retrieve(t));
	if (cmp == 1) {
		t->right = insert(t->right, x);
	} else if (cmp == 0) {
		return t ; // has this element
	} else if (cmp == -1) {
		t->left = insert(t->left, x);
	}
	return t;
}

void printTree(Tree t, int order) {
	if (t == NULL) return;
	if (order == ORDER_PRE) {
		printTree(t->left, order);
		printf("%.1f\n", retrieve(t));
		printTree(t->right, order);
	} else if (order == ORDER_MID) {
		printf("%.1f\n", retrieve(t));
		printTree(t->left, order);
		printTree(t->right, order);
	} else if (order == ORDER_POST) {
		printTree(t->left, order);
		printTree(t->right, order);
		printf("%.1f\n", retrieve(t));
	}
}

PtrToNode findMin(Tree t) {
	if (t == NULL) return NULL;
	if (t->left == NULL) return t;
	return findMin(t->left);
}

PtrToNode findMax(Tree t) {
	if (t == NULL) return NULL;
	while (t->right != NULL)
		t = t->right;
	return t;
}

Tree deleteNode(Tree t, ElementType x) {
	if (t == NULL ) {
		printf("error: element not found\n");
		return;
	}
	PtrToNode tmpNode;
	int cmp = compare(x, retrieve(t));
	if (cmp == 1) {
		t->right = deleteNode(t->right, x);
	} else if (cmp == -1) {
		t->left = deleteNode(t->left, x);
	} else {
		if (t->left && t->right) {
			tmpNode = findMin(t->right);
			t->ele = tmpNode->ele;
			t->right = deleteNode(t->right, t->ele);
		} else {
			tmpNode = t;
			if (t->left == NULL) t = t->right;
			else t = t->right;
			freeNode(tmpNode);
		}
	}
	return t;
}